# define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>



struct ListNode {
    int val;
    struct ListNode* next;
    
};

bool hasCycle(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;


        if (fast == slow)
        {
            struct ListNode* cur = fast, * prev = head;
            int pos = 0;


            while (prev != cur)
            {
                prev = prev->next;
                cur = cur->next;
                pos++;
            }
        }
    }
}


    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* cur = NULL;
        struct ListNode* prev = NULL;
        while (head != NULL)
        {
            cur = head->next;
            head->next = prev;
            prev = head;
            head = cur;
        }

        return prev;
    }


    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* prev = head;
        struct ListNode* cur = head;
        while (cur != NULL && cur->next != NULL)
        {
            prev = prev->next;
            cur = cur->next->next;
        }
        return prev;
    }



    bool chkPalindrome(struct ListNode* A) {
        struct ListNode* prev = A, * cur = A;
        cur = middleNode(A);
        cur = reverseList(cur);
        while (prev && cur)
        {
            if (prev->val != cur->val)
            {
                return false;
            }
            prev = prev->next;
            cur = cur->next;
        }
        return true;
    }
